package com.vincent.algorithms.sort;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 快速排序  快，而且效率高! 它是处理大数据最快的排序算法之一
 * 基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，
 * 则可分别对这两部分记录继续进行排序，以达到整个序列有序
 *
 * 平均时间复杂度O(nlogn)  在所有平均时间复杂度为O(nlogn) 的算法中  快速排序的平均性能是最好的(待考证)
 * 最坏情况时间复杂度O(n^2) 即本来是逆序的
 * 最好情况时间复杂度O(nlogn)
 * 空间复杂度 O(nlogn)
 * 稳定性 不稳定     比如：{42 30 21  50  21}  第一步 后面的21就放到前面了  网上可以找下需要辅助空间的稳定版本
 *
 * Created by yangwenchang on 2017/8/23.
 */
public class QuickSort implements Sort{
    @Override
    public <T> void sort(T[] array, Comparator<? super T> c) {

    }
    public <T> void sort(T[] array,int start,int end, Comparator<? super T> c){
        sort2(array,start,end,c);
    }

//    中间数 从(end-start)/2 位置取  先交换 再移动
//    其实比较麻烦 更推荐下面的写法
    public <T> void sort2(T[] array,int start,int end, Comparator<? super T> c) {
        if (start>=end){
            return;
        }
        System.out.println(Arrays.asList(array)+"start:"+start+"--end:"+end);
        int pivotIndex = (start+end)/2;
        System.out.println("pivot:"+array[pivotIndex]);
        int left = start;
        int right = end;

        // 第一阶段 交换
        while (left<pivotIndex&&right>pivotIndex){
            // 找到左边一个大于中间数的待移动数据
            while (left<pivotIndex){
                if (c.compare(array[left],array[pivotIndex])>0){
                    break;
                }else {
                    left++;
                }
            }
            // 找到右边一个小于中间数的待移动数据
            while (right>pivotIndex){
                if (c.compare(array[right],array[pivotIndex])<0){
                    break;
                }else {
                    right--;
                }
            }
            // 如果两变都找到了 则交换数据
            if(left<pivotIndex&&right>pivotIndex){
                Sort.swap(array,left,right);
            }
        }
        // 第二阶段 移动中间数
        T pivot = array[pivotIndex];
        while (left<pivotIndex){
            if (c.compare(array[left],array[pivotIndex])>0){
//                pivotIndex left piovtIndex-1 三个位置数据交换 并且 pivotIndex--
                array[pivotIndex] = array[left];
                array[left]=array[pivotIndex-1];
                array[--pivotIndex] = pivot;
            }{
                left++;
            }
        }
        while (right>pivotIndex){
            if (c.compare(array[right],array[pivotIndex])<0){
//                pivotIndex right piovtIndex-1 三个位置数据交换 并且 pivotIndex++
                array[pivotIndex] = array[right];
                array[right]=array[pivotIndex+1];
                array[++pivotIndex] = pivot;
            }{
                right--;
            }
        }

        System.out.println(Arrays.asList(array));
        sort2(array,start,pivotIndex-1,c);
        sort2(array,pivotIndex+1,end,c);
    }


    /**
     * 选取第一元素为基准元素
     *
     *
     * @param array
     * @param start
     * @param end
     * @param c
     * @param <T>
     */
    public <T> void sort1(T[] array,int start,int end, Comparator<? super T> c) {

        if (start>=end){
            return;
        }

        int left = start;
        int right = end;
//        默认去第一个数为基准 保存到临时变量povit上 这时可以视为array[left]为空 然后开启交替找大小值
        T povit = array[left];
        while (left<right){
            // 找到右边一个小于中间数的数据 放到array[left](即空着的)位置上  放置后右边array[right]位置视为空着
            while (left<right){
                if (c.compare(array[right],povit)<0){
                    array[left] = array[right];
                    break;
                }else {
                    right--;
                }
            }
            // 找到左边一个大于中间数的数据放到 array[right](即空着的)位置上  放置后右边array[left]位置视为空着
            while (left<right){
                if (c.compare(array[left],povit)>0){
                    array[right] = array[left];
                    break;
                }else {
                    left++;
                }
            }
//          前后各扫描一次后  基准值位置重置
            array[left] = povit;
        }

        sort1(array,start,left-1,c);
        sort1(array,left+1,end,c);

    }

    /**
     * 跟上面的思路相同  只是写法更紧凑
     *
     * @param array
     * @param start
     * @param end
     * @param c
     * @param <T>
     */
    public <T> void sort3(T[] array,int start,int end, Comparator<? super T> c) {

        if (start>=end){
            return;
        }

        int left = start;
        int right = end;
//        默认去第一个数为基准 保存到临时变量povit上 这时可以视为array[left]为空 然后可以后前交替找需要挪动的值
        T povit = array[left];
        while (left<right){
            // 找到右边一个小于中间数的数据 放到array[left](即空着的)位置上  放置后右边array[right]位置视为空着
            while (left<right && c.compare(array[right],povit)>=0){
                right--;
            }
            if(left<right){
                array[left] = array[right];
            }
            // 找到左边一个大于中间数的数据放到 array[right](即空着的)位置上  放置后右边array[left]位置视为空着
            while (left<right && c.compare(array[left],povit)<=0){
                left++;
            }
            if (left<right){
                array[right] = array[left];
            }
        }
//      基准值位置重置
        array[left] = povit;

        sort3(array,start,left-1,c);
        sort3(array,left+1,end,c);

    }



        public static void main(String[] args) {

        Integer[] arr = {5,80,6,43,80,12,53,80,13};
        System.out.println(Arrays.asList(arr));
        new QuickSort().sort3(arr,0,arr.length-1,(x,y)->x-y);
        System.out.println(Arrays.asList(arr));

    }
}
